package edu.bupt.c2string;

public class T07WildcardMatching {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] cache = new boolean[m+1][n+1];

        cache[0][0] = true;
        for (int j=1;j<=n;j++){
            if ('*' == p.charAt(j-1)){
                cache[0][j] = true;
            }else{
                break;
            }
        }


        for(int i=1;i<=m;i++){
            for (int j=1;j<=n;j++){
                if ('?' == p.charAt(j-1) || s.charAt(i-1)==p.charAt(j-1) ){
                    cache[i][j] = cache[i-1][j-1];
                } else if ('*' == p.charAt(j-1)){
                    cache[i][j] = cache[i][j-1] || cache[i-1][j];
                }else{
                    cache[i][j] = false;
                }
            }
        }


        return cache[m][n];
    }

    public static void main(String[] args) {
        boolean adceb = new T07WildcardMatching().isMatch("cb", "?a");
        System.out.println("1");
    }

}
